import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * @ClassName Offer48
 * @Description 剑指 Offer 48. 最长不含重复字符的子字符串
 * @Author clockTown
 * @Date 2021/8/21 16:03
 * @Version 1.0
 */
class Offer48 {
}

/**
 * v0 队列
 */
class Offer48V0 {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] chars = s.toCharArray();
        Queue<Character> queue = new LinkedList<>();
        int maxLength = 1;
        queue.offer(chars[0]);
        for (char c : chars) {
            while (!queue.isEmpty() && queue.contains(c)) {
                queue.poll();
            }
            queue.offer(c);
            maxLength = Math.max(queue.size(), maxLength);
        }
        return maxLength;
    }
}

/**
 * v1 动态规划 + 哈希表
 */
class Offer48V1 {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0;

        for(int j = 0; j < s.length(); j++) {
            // 获取索引 i
            int i = dic.getOrDefault(s.charAt(j), -1);
            // 更新哈希表
            dic.put(s.charAt(j), j);
            // dp[j - 1] -> dp[j]
            tmp = tmp < j - i ? tmp + 1 : j - i;
            // max(dp[j - 1], dp[j])
            res = Math.max(res, tmp);
        }
        return res;
    }
}